The present invention relates to a system for providing reversible variable length codes. The present invention is used for a digital communication system which transmits information through encoding to 1 and/or 0. The present invention is used in particular in picture transmission, voice transmission, and/or data transmission field.
A variable length code is defined as a code which has variable length for each symbol. When a shorter code is assigned to symbol which appears often than a symbol which appears with small probability, the total code length for a full text is shortened as compared with that of the case when a fixed length code is used, and therefore, the transmission efficiency is improved.
A reversible code is defined as a code which is decoded not only in forward direction of a code, but also in backward direction of a code. A reversible code is advantageous when some bit error happens. Because of a bit error, even when a decoding in forward direction is impossible, a decoding in backward direction might be possible. The backward decoding is advantageous in particular for reconstruction of video signals in backward direction when some bits are lost in transmission.
A reversible code must satisfy two conditions, a prefix condition, and a suffix condition, in order to make the instantaneous decoding, which is defined that an end or start of a symbol is recognized just when each bit is received. The prefix condition is defined that any code is not included in a former part or prefix portion of a longer code, and the suffix condition is defined that any code is not included in a rear part or suffix portion of a longer code.
Conventionally, a fixed length code and a B2 code have been known as a reversible code which satisfies also said prefix condition and said suffix condition. A B2 code is described in "Coding of digital TV signal; Variable length codes applied to DCT coefficients" by M. Barbero et al, in Digital TV Signal Coding 1989.
A fixed length code has the feature that an automatic synchronization between symbols is established in both forward direction and in backward direction since each symbol has the same bit length as each other.
A B2 code is constituted by combination of two bits of a continuous flag bit and an information bit. The continuous flag bit is, for instance, 0 for terminated bit, and 1 for continued bit. As a continuous flag bit indicates termination of a symbol, an instantaneous decoding in both forward direction and backward direction is possible.
Examples of the fixed length code and the B2 code are shown in the tables 1 and 2, where table 1 shows codes for alphabetic symbols (S1), and table 2 shows codes for interframe motion vector symbols (S2) in image encoding. The value P.sub.1 shows occurrence probability of each alphabetical symbols, the value P.sub.2 shows occurrence probability of each vector symbols, C.sub.12, and C.sub.22 are fixed length codes for P.sub.1 and P.sub.2, respectively, and C.sub.13 and C.sub.23 are B2 codes for P.sub.1 and P.sub.2, respectively.
The conventional variable length codes C.sub.11 and C.sub.21 are shown in the tables 1 and 2 (Huffman code) for interest. Those codes are decodable only in forward direction.
In the tables 1 and 2, a fixed length code has the disadvantage that an average code length is long, and therefore, the transmission efficiency of information is low.
A B2 code has the disadvantage that it must have a pair of decoding tables for forward direction decoding and backward direction decoding, respectively, as a code itself is asymmetrical.
A non-reversible variable length code has the disadvantage that it can not be decoded in backward direction although the average code length is short.
TABLE 1 __________________________________________________________________________ Occurrence Symmetrical Asymmetrical probability Huffman (C.sub.11) Fixed (C.sub.12) B2 (C.sub.13) reversible (C.sub.14) reversible (C.sub.15) (S.sub.1) (P.sub.1) L Code L Code L Code L Code L Code __________________________________________________________________________ E 0.14878570 3 001 5 00001 2 00 3 000 3 001 T 0.09354149 3 110 5 00010 2 01 3 111 3 110 A 0.08833733 4 0000 5 00011 4 1000 4 0110 4 0000 O 0.07245796 4 0100 5 00100 4 1001 4 1001 4 0100 R 0.06872164 4 0101 5 00101 4 1100 5 00100 4 1000 N 0.06498532 4 0110 5 00110 4 1101 5 11011 4 1010 H 0.05831331 4 1000 5 00111 6 101000 5 01010 4 0101 I 0.05644515 4 1001 5 01000 6 101001 5 10101 5 11100 S 0.05537763 4 1010 5 01001 6 101100 5 01110 5 01100 D 0.04376834 5 00010 5 01010 6 101101 5 10001 5 00010 L 0.04123298 5 00011 5 01011 6 111000 6 001100 5 10010 U 0.02762209 5 10110 5 01100 6 111001 6 110011 5 01111 P 0.02575393 5 10111 5 01101 6 111100 6 010010 5 10111 F 0.02455297 5 11100 5 01110 6 111101 6 101101 5 11111 M 0.02361889 5 11110 5 01111 8 10101000 6 011110 6 111101 C 0.02081665 5 11111 5 10000 8 10101001 6 100001 6 101101 W 0.01868161 6 011100 5 10001 8 10101100 7 0010100 6 000111 G 0.01521216 6 011101 5 10010 8 10101101 7 1101011 6 011101 Y 0.01521216 6 011110 5 10011 8 10111000 7 0011100 6 100111 B 0.01267680 6 011111 5 10100 8 10111001 7 1100011 7 1001101 V 0.01160928 6 111011 5 10101 8 10111100 7 0100010 8 01110011 K 0.00867360 7 1110100 5 10110 8 10111101 7 1011101 8 00011011 X 0.00146784 8 11101011 5 10111 8 11101000 8 00111100 9 000110011 J 0.00080064 9 111010101 5 11000 8 11101001 9 001010100 10 001101011 Q 0.00080064 10 1110101000 5 11001 8 11101100 10 0010110100 11 00011010011 Z 0.00053376 10 1110101001 5 11010 8 11101101 10 1101001011 12 000110100011 Average length 4.15572453 5.00000000 4.70189428 4.69655657 4.36068869 Prior Art Invention __________________________________________________________________________
TABLE 2 __________________________________________________________________________ Occurrence Symmetrical Asymmetrical probability Huffman (C.sub.21) Fixed (C.sub.22) B2 (C.sub.23) reversible (C.sub.24) reversible (C.sub.25) (S.sub.2) (P.sub.2) L Code L Code L Code L Code L Code __________________________________________________________________________ MV1 0.40111506 1 1 6 000001 2 00 1 0 1 1 MV2 0.12033451 3 010 6 000010 2 01 3 111 3 010 MV3 0.10830107 3 011 6 000011 4 1000 3 101 3 000 MV4 0.10428991 4 0010 6 000100 4 1001 4 1001 4 0110 MV5 0.09987765 4 0011 6 000101 4 1100 5 11011 5 00100 MV6 0.03744409 5 00010 6 000110 4 1101 5 10001 5 01110 MV7 0.03208920 5 00011 6 000111 6 101000 6 110011 6 001100 MV8 0.01403903 7 0000110 6 001000 6 101001 7 1101011 7 0011110 MV9 0.01383847 7 0000111 6 001001 6 101100 7 1100011 7 0111100 MV10 0.00762119 7 0000000 6 001010 6 101101 7 1000001 7 0011100 MV11 0.00734041 8 00001010 6 001011 6 111000 8 11000011 8 00111110 MV12 0.00730029 8 00001011 6 001100 6 111001 8 10000001 8 01111110 MV13 0.00722007 8 00001000 6 001101 6 111100 9 110101011 8 01111100 MV14 0.00701951 8 00001001 6 001110 6 111101 9 110010011 9 011110100 MV15 0.00681896 8 00000110 6 001111 8 10101000 9 110000011 9 001110100 MV16 0.00661840 8 00000111 6 010000 8 10101001 9 100000001 9 011111110 MV17 0.00413149 8 00000010 6 010001 8 10101100 10 1101001011 10 0011111100 MV18 0.00162452 10 0000010110 6 010010 8 10101101 10 1100000011 10 0111110100 MV19 0.00160847 10 0000010111 6 010011 8 10111000 10 1000000001 10 0011101100 MV20 0.00135176 10 0000010100 6 010100 8 10111001 11 11010101011 10 0111101100 MV21 0.00134374 10 0000010101 6 010101 8 10111100 11 11010001011 11 01111101100 MV22 0.00132368 10 0000010010 6 010110 8 10111101 11 11001010011 11 01111011100 MV23 0.00128357 10 0000010011 6 010111 8 11101000 11 11000100011 11 00111011100 MV24 0.00058162 11 00000100010 6 011000 8 11101001 11 11000000011 11 01111011110 MV25 0.00057359 11 00000100011 6 011001 8 11101100 11 10000100001 11 00111011110 MV26 0.00056958 11 00000100000 6 011010 8 11101101 11 10000000001 12 001110110100 MV27 0.00056156 11 00000100001 6 011011 8 11111000 12 110100001011 12 011111011100 MV28 0.00054151 11 00000011110 6 011100 8 11111001 12 110010010011 12 011110110100 MV29 0.00052145 11 00000011111 6 011101 8 11111100 12 110000000011 12 011111010100 MV30 0.00050139 11 00000011100 6 011110 8 11111101 12 100001100001 12 011111011110 MV31 0.00048134 11 00000011101 6 011111 10 1010101000 12 100000000001 12 001110111110 MV32 0.00046128 11 00000011010 6 100000 10 1010101001 13 1101010101011 12 011110111110 MV33 0.00044123 11 00000011011 6 100001 10 1010101100 13 1101001001011 13 0111101101100 MV34 0.00042919 11 00000011001 6 100010 10 1010101101 13 1101000001011 13 0111110101100 MV35 0.00040112 11 00000011000 6 100011 10 1010111000 13 1100101010011 13 0011101101100 Average length 3.02351332 6.000000 3.28314328 3.20279551 3.19433165 Prior Art Invention __________________________________________________________________________